//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

/**
 * 哈希冲突解决，开散列 哈希桶
 */
public class hashBuket {
    private int capacity = 10;
    private int size = 0;
    private List[] arr = new List[capacity];
    private Double loadFactor = 0.75;

    static class List {
        int val;
        List next;

        public List(int val) {
            this.val = val;
        }

        public void addEnd(List head, int val) {
            while(head.next != null) {
                head = head.next;
            }

            head.next = new List(val);
        }
    }
    public hashBuket() {
    }

    public void add(int val) {
        if (this.isFactor()) {
            this.expand();
        }

        int index = Math.abs(val % this.capacity);
        if (this.arr[index] == null) {
            this.arr[index] = new List(val);
        } else {
            this.arr[index].addEnd(this.arr[index], val);
        }

        ++this.size;
    }

    public boolean poll(int val) {
        int index = Math.abs(val % this.capacity);
        if (this.arr[index] == null) {
            return false;
        } else {
            if (this.arr[index].val == val) {
                this.arr[index] = this.arr[index].next;
            } else {
                List tmp = this.arr[index];
                List prev;
                for(prev = null; tmp != null && tmp.val != val; tmp = tmp.next) {
                    prev = tmp;
                }
                if (tmp == null) {
                    return false;
                }
                prev.next = tmp.next;
            }
            return true;
        }
    }

    public boolean contain(int val) {
        int index = Math.abs(val % this.capacity);

        List tmp;
        for(tmp = this.arr[index]; tmp.val != val; tmp = tmp.next) {
        }

        return tmp == null ? false : true;
    }

    public List getList(int val) {
        int index = Math.abs(val % this.capacity);

        List tmp;
        for(tmp = this.arr[index]; tmp.val != val; tmp = tmp.next) {
        }

        return tmp;
    }

    public void showElement() {
        for(int i = 0; i < this.arr.length; ++i) {
            List tmp = this.arr[i];
            if (tmp != null) {
                System.out.print("( ");

                while(tmp != null) {
                    System.out.print(tmp.val + " ");
                    tmp = tmp.next;
                }

                System.out.print(") ");
            }
        }

    }

    public int getCapacity() {
        return this.capacity;
    }

    private void expand() {
        List[] newArr = new List[this.capacity * 2];
        this.capacity *= 2;

        for(int i = 0; i < this.arr.length; ++i) {
            for(List tmp = this.arr[i]; tmp != null; tmp = tmp.next) {
                int index = Math.abs(tmp.val % this.capacity);
                if (newArr[index] == null) {
                    newArr[index] = new List(tmp.val);
                } else {
                    newArr[index].addEnd(newArr[index], tmp.val);
                }
            }
        }

        this.arr = newArr;
    }

    private boolean isFactor() {
        return (double) this.size * 1.0 / (double) this.capacity >= this.loadFactor;
    }

}
